package LeetCode;

public class LC_375_GuessNumberHigherorLowerII {

    public static void main(String[] args) {

    }

    public class Solution_1 {
        public int getMoneyAmount(int n) {
            int[][] dp = new int[n][n];
            for (int i = 0; i < n - 1; i++) dp[i][i + 1] = i + 1;
            for (int len = 2; len < n; len++) {
                for (int i = 0; i + len < n; i++) {
                    int j = i + len;
                    for (int k = i + 1; k < j; k++) {
                        int cur = k + 1 + Math.max(dp[i][k - 1], dp[k + 1][j]);
                        if (dp[i][j] == 0 || dp[i][j] > cur) dp[i][j] = cur;
                    }
                }
            }
            return dp[0][n - 1];
        }
    }

    public class Solution_2 {
        public int getMoneyAmount(int n) {
            int[][] dp = new int[n + 1][n + 1];
            return solve(dp, 1, n);
        }

        int solve(int[][] dp, int L, int R) {
            if (L >= R) return 0;
            if (dp[L][R] != 0) return dp[L][R];
            dp[L][R] = 0x7FFFFFFF;
            for (int i = L; i <= R; i++) {
                dp[L][R] = Math.min(dp[L][R], i + Math.max(solve(dp, L, i - 1), solve(dp, i + 1, R)));
            }
            return dp[L][R];
        }
    }
}